#!/usr/bin/python3


def coin_change_origin(coins: list[int], amount: int):
    """
    换硬币。
    """

    def dp(n: int) -> int:
        """
        动态规划。
        """
        if n < 0:
            return -1

        if n == 0:
            return 0

        # 求最小值，所以初始化为正无穷
        res = float("INF")

        # 循环以获得当前状态的最优解；
        for coin in coins:
            # 获取子问题的解；
            subproblem = dp(n - coin)

            # 判断子问题是否有解；
            if subproblem >= 0:  # 若有解；
                res = min(res, 1 + subproblem)
            else:  # 若无解；
                pass

        return res if res != float("INF") else -1

    return dp(amount)


def coin_change_menorial(coins: list[int], amount: int) -> int:
    """
    换硬币。
    """
    memo: list = [0] * (amount + 1)

    def dp(n: int):
        """
        docstring
        """
        if memo[n] > 0:
            return memo[n]

        if n == 0:
            return 0
        if n < 0:
            return -1

        res = float("INF")

        for coin in coins:
            subproblem = dp(n - coin)
            # 子问题无解，跳过
            if subproblem == -1:
                continue
            res = min(res, 1 + subproblem)

        memo[n] = res if res != float("INF") else -1

        return memo[n]

    return dp(amount)


def coin_change_table(coins: list[int], amount: int) -> int:
    """
    换硬币。
    """

    def dp(n: int):
        """
        docstring

        """
        if n < 0:
            return -1

        dp: list[int] = [amount + 1] * (amount + 1)

        dp[0] = 0
        for i in range(1, n + 1):
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], 1 + dp[i - coin])

        return dp[n]

    return dp(amount)


if __name__ == "__main__":
    # fun([1, 5, 11], 15)
    print(coin_change_table([1, 5, 11], 15))
